import gmpy2
from Crypto.Util.number import *
import time

def Pollards_p_1(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a - 1, N)
        if res != 1 and res != N:
            print('n =', n)
            print('p =', res)
            return res
        n += 1


t1=time.time()
print(t1)
e = 0x10001
n= 74186574773094914200793316482026737888029459954999794709543067320974116632360492502173041497419087333648379365916337386550501241512964933930920296213690546163903568060144802072907352410289817238773935298058120931756211949834537184580004146147011906046925415102068575128637685130857734165699709372402386494273872659178012812526452750326989859184669742220784770554396100994762970689631211088819152161793291234247565544015273517360237216604449262594676097450253587397009568654574908264827845608948630311193568589876380198206712600988473836479191942204078557360048382752212611123994666378998631100625416354771446453086403887608196718848828625043329354162548697948577052390304018564048925705585294154706019905390513046572500156873454890769579711221993930461212240313285542036999394273974709021139378172951930880526726041086399628443532394752602706140809701992841699198694380383517720343104199384350206567999623946695141110150446707486501918242049206119419186532290441052193142213376394976152405430947027759650651324035945611520584745465738065561870522118727442644801612767924448608030907993546440313565267711970419923753819799134348966623813216535312453229146158725554129427490029779887349549098126474452019254802523030667862456482358940609
c= 13798798797311476147972744890014796424563856033617455941174937051525031166167343556982289358877693303965831886573992503232015737346347020221617100959059102457815822751424439757088461317263736496066346047076722459059162032717547275063048254795157994106940784171252770377103146318795308076599248001282926520785876739891975082930962806865650282063600060574004255805020507563922671004042462400063066768800905559120349363170738586133483692175136730576859224176745569188789673254081647929259892325047427578860871500105880072951421944745281483929404453324499215859258361264558778834432647664456023208734349987929389782132823526018790602652352521007729672944487319519583975460558935365007888702783469129419895548188840781686738671955620339978985745783851389680095270702793801729975192698356855018330129058658904949279585905797213388910664491314145663759413554946874511881302855712885467994028085520244731561853588964212910529043604693061801895639656170650487890961433161392259934391542460134390584337120430272745712085212448898617269092305139925012285770050309750988761863061415329411345368532763833992063446541356805869749812491756359730516697166371876947390246841987901107310535600052879474086698163101234177250689444309194098222304511589220

p = Pollards_p_1(n)
q = n // p
assert p * q == n
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
t2=time.time()
print(t2-t1)